import numpy as np
# 贪心算法
# class Solution(object):
#     def isMatch(self, s, p):
#         """
#         :type s: str
#         :type p: str
#         :rtype: bool
#         """
#         def judge(s, item):
#             index = 0
#             for i in range(item[0], item[1]):
#                 if s[index] == p[i]:
#                     index += 1
#                 else:
#                     if p[i] == '?':
#                         index += 1
#                     else:
#                         return False
#             return True
#
#         if len(p) == 0:
#             if len(s) == 0:
#                 return True
#             else:
#                 return False
#         l = []
#         start_index = 0
#         end_index = 0
#         while end_index < len(p):
#             if p[end_index] != '*':
#                 end_index += 1
#             else:
#                 if end_index > start_index:
#                     l.append([start_index, end_index])
#                 start_index = end_index + 1
#                 end_index = start_index
#         if p[end_index - 1] != '*':
#             l.append([start_index, end_index])
#         if len(s) == 0 and len(l) > 0:
#             return False
#         if len(l) == 0:
#             return True
#         if len(l) == 1:
#             if l[0][0] == 0 and l[0][1] == len(p):
#                 if len(s) == len(p):
#                     return judge(s, l[0])
#                 else:
#                     return False
#         index = 0
#         length = len(l)
#         for i, item in enumerate(l):
#             if i == 0 and item[0] == 0:
#                 if len(s[index:]) >= item[1] - item[0]:
#                     if judge(s[:item[1]], item):
#                         index += item[1]
#                     else:
#                         return False
#                 else:
#                     return False
#             else:
#                 if i == length - 1 and item[1] == len(p):
#                     if len(s[index:]) >= item[1] - item[0]:
#                         if judge(s[item[0] - item[1]:], item):
#                             return True
#                         else:
#                             return False
#                     else:
#                         return False
#                 else:
#                     flag = False
#                     while index + item[1] - item[0] <= len(s):
#                         if judge(s[index: index + item[1] - item[0]], item):
#                             flag = True
#                             index += item[1] - item[0]
#                             break
#                         else:
#                             index += 1
#                     if not flag:
#                         return False
#         return True

# 动态规划

class Solution(object):
    def isMatch(self, s, p):
        len_p = len(p)
        len_s = len(s)
        DP = [[False for _ in range(len_p + 1)]for _ in range(len_s + 1)]
        for i in range(1, len_s + 1):
            DP[i][0] = False
        DP[0][0] = True
        for j in range(1, len_p + 1):
            if p[j - 1] == '*':
                DP[0][j] = DP[0][j - 1]
            else:
                DP[0][j] = False
        for j in range(1, len_p + 1):
            if p[j - 1] == '*':
                flag = False
                for i in range(1, len_s + 1):
                    if not flag:
                        DP[i][j] = DP[i - 1][j - 1] or DP[i][j - 1]
                        if DP[i][j]:
                            flag = True
                    else:
                        DP[i][j] = True
            else:
                for i in range(1, len_s + 1):
                    if p[j - 1] == '?':
                        DP[i][j] = DP[i - 1][j - 1]
                    else:
                        DP[i][j] = DP[i - 1][j - 1] and s[i - 1] == p[j - 1]

        return DP[len_s][len_p]



data = Solution()
s = "abcabczzzde"
p = "*abc???de*"
print(data.isMatch(s, p))